The Problem of Skewed BSTs

Inserting elements in a sorted order can lead to a "worst-case" scenario, where the tree degrades into a linked list.

Recall: BST search / insert / delete run in \(O(h)\) where \(h\) is the tree height.

  • Balanced (ideal): \(h \approx \lfloor \log_2 n \rfloor \Rightarrow O(\log n)\).
  • Skewed (worst): \(h = n-1 \Rightarrow O(n)\) — effectively a linked list.

Inserting already sorted data produces a right-skewed tree (reverse-sorted → left-skewed).

Motivation for AVL trees: Detect height imbalances early and perform rotations to keep \(h = \Theta(\log n)\), preserving efficiency.

Skewed Tree Performance

Behaves like a linked list. Search time is\(O(n)\).

Balanced Tree Performance

Height is minimized. Search time is\(O(\log n)\).